package com.mercator.client.graph;


/**
 *  Graph.java
 *  
 *  Undirected graph data type implemented using a symbol table
 *  whose keys are any element of type T and whose values are nodes
 *  in the graph.
 *
 *  Remarks
 *  -------
 *   - Parallel edges are not allowed
 *   - Self-loop are allowed
 *   - Adjacency lists store many different copies of the same
 *     String. You can use less memory by interning the strings.
 *
 *  Retrieved from http://www.cs.princeton.edu/introcs/45graph/
 *  
 *  Modified by:
 *  @author Avner Maiberg (Av.Net)
 *  @author Emma Strubell (Etzrubal)
 *  COS350 - Latour
 *  April 15, 2010
 */

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

public abstract class Graph<T extends Comparable<? super T>, N extends Node< T,N>> extends Container<T,N> 
{
	// a table mapping values to Nodes in this graph
	protected HashMap<T,N> nodes;
	
	// a list of all the edges in this graph
	protected ArrayList<Edge<? extends T,N>> edges;
	
	// highest edge weight in this graph
	protected int maxWeight;

	/**
	 * Constructor: Creates an empty graph.
	 */
	public Graph() {
		nodes = new HashMap<T,N>();
		edges = new ArrayList<Edge<? extends T,N>>();
		maxWeight = 1;
	}


	/**
	 * @return number of vertices in the graph
	 */
	public int order() {
		return nodes.size();
	}

	/**
	 * @return number of edges in the graph
	 */
	public int size() {
		return edges.size();
	}

	/**
	 * @param n Node of which to determine the degree
	 * @return return the degree of node n (number of incident edges)
	 */
	public int degree(N n) {
		if (!nodes.containsKey(n.element))
			return -1;
		else
			return nodes.get(n.element).getDegree();
	}
	
	public int degree(T n) {
		if (!nodes.containsKey(n))
			return -1;
		else
			return nodes.get(n).getDegree();
	}

	/**
	 * Adds Node with value w to Node with value v's set of neighbors and 
	 * vice versa.
	 * 
	 * @param v value of Node to connect to Node with value w
	 * @param w value of Node to connect to Node with value v
	 */
	public void addEdge(T v, T w)
	{
		if (!hasEdge(v, w))
		{
			edges.add(new Edge<T,N>(nodes.get(v), nodes.get(w)));
		}
		
	}
	
	/**
	 * Adds Node with value w to Node with value v's set of neighbors and 
	 * vice versa whose edge has the given weight.
	 * 
	 * @param v value of Node to connect to Node with value w
	 * @param w value of Node to connect to Node with value v
	 * @param weight the weight of the Edge between these Nodes
	 */
	public void addEdge(T v, T w, int weight)
	{
		if (!hasEdge(v, w))
		{
			edges.add(new Edge<T,N>(weight, nodes.get(v), nodes.get(w)));
		    if(weight > maxWeight)
			maxWeight = weight;
		}
		
	}

	
    
	/**
	 * Add a new Node with value n (if vertex does not yet exist)
	 * @param n value to be represented by new vertex
	 */
/*
	public void addVertex(T n) {
	    if (!hasVertex(n))
		nodes.put(n, N);
	}
	*/
	public void addVertex(N n) {
	    if (!hasVertex(n.element)){
	    	nodes.put(n.getElement(), n.getThis());
	    }
	    for(N node : n.adjacentNodes)
	    	nodes.get(n.getElement()).connect(node);
	}
	
	/**
	 * @return iterator over all vertices in graph
	 */
	public Iterable<T> vertices() {
		return nodes.keySet();
	}

	/**
	 * @param v value to check for in the graph
	 * @return boolean true if a Node with value v is in the graph, false if not
	 */
	public boolean hasVertex(T v) {
		return nodes.get(v)  == null ? false : true;
	}
	
	public boolean hasVertex(N v) {
		return nodes.get(v.getElement()) == null ? false : true;
		}

	/**
	 * @return boolean true if edge exists between Nodes with values v and w,
	 * false otherwise.
	 */
	public boolean hasEdge(T v, T w) {
		if (!hasVertex(v) || !hasVertex(w))
			return false;
		return nodes.get(v).adjacentNodes.contains(nodes.get(w));
	}

	/**
	 * @return String a string representation of the graph
	 */
	/*
	@Override
	public String toString() {
		LinkedList<? extends T> keys = new LinkedList<T>(nodes.keySet());
		//Collections.sort(keys);
		String s = "";
		for (T v : keys) {
			int i = 1;
			s += "" + v + "  || \n";
			for (Node<? extends T,N> w : nodes.get(v).adjacentNodes){ 
				s += i + "." + w + "\n";
			i++;}
			s += "\n";
		}
		return s;
	}
	*/
	/**
	 * Returns an iterator over the adjacent nodes of v.
	 * @param v the node
	 * @return Iterable<Node<T>>
	 */
	public Iterable<N> adjacentTo(T v) {
		// return empty set if vertex isn't in graph
		if (!hasVertex(v))
			return new HashSet<N>();
		else
			return nodes.get(v).adjacentNodes;
	}
	
	public Iterable<N> nodes() {
		// return empty set if vertex isn't in graph
		return nodes.values();
	}
	
	public void remove ( T t ){
		nodes.remove(t);
	}


	@Override
	public Iterator<N> iterator() {
		return nodes.values().iterator();
	}
	
	public Collection<N> values() {
		return nodes.values();
	}
	
	public void connect(N v1, N v2){
		if(hasVertex(v1) && hasVertex(v2))
			v2.connect(v1); 
			v1.connect(v2);
	}

	@Override
	public Iterable<T> getVals() {
		return nodes.keySet();
	}


	@Override
	public Collection<N> getCol() {
		return nodes.values();
	}


	@Override
	public Iterable<N> getNodes() {
		return nodes.values();
	}


	@Override
	public void connect(T elem1, T elem2) {
		if(hasVertex(elem1) && hasVertex(elem2)){
			find(elem1).connect(find(elem2));
			find(elem2).connect(find(elem1));
		}
	}

	@Override
	public void removeAll() {
		nodes.clear();
	}

	@Override
	public void add(N n) {
		if(!hasVertex(n))
			nodes.put(n.element, n);
	}


	@Override
	public N find(N n) {
		return nodes.get(n.element);
	}

	@Override
	public N find(T t) {
		return nodes.get(t);
	}

	@Override
	public Collection<T> getValCol(){
		return nodes.keySet();
	}
	
	
}
